use std::cmp::min;

struct Solution {}

impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let n = nums1.len() + nums2.len();
        let kth = if n % 2 == 1 { n / 2 + 1 } else { n / 2 };
        let (left_a, left_b) = find_k_th(&nums1, 0, &nums2, 0, kth);
        println!("a: [{}, ), b: [{}, ), k: {}", left_a, left_b, kth);
        let kthNum =
            if nums1.len() == 0 || left_a == 0 { nums2[left_b - 1] } //
            else if nums2.len() == 0 || left_b == 0 { nums1[left_a - 1] } //
            else if nums1[left_a - 1] <= nums2[left_b - 1] { nums2[left_b - 1] } //
            else { nums1[left_a - 1] };
        if n % 2 == 1 { kthNum as f64 } else {
            let rightNum =
                if left_a == nums1.len() { nums2[left_b] } //
                else if left_b == nums2.len() { nums1[left_a] } //
                else if nums1[left_a] >= nums2[left_b] { nums2[left_b] } //
                else { nums1[left_a] };
            (kthNum + rightNum) as f64 / 2.0
        }
    }
}

pub fn find_k_th(
    a: &Vec<i32>,
    left_a: usize,
    b: &Vec<i32>,
    left_b: usize,
    k: usize,
) -> (usize, usize) {
    if k == 0 {
        (left_a, left_b)
    } else if left_a == a.len() {
        (left_a, left_b + k)
    } else if left_b == b.len() {
        (left_a + k, left_b)
    } else {
        let half = if k / 2 > 0 { k / 2 } else { 1 };
        let most_a = min(a.len() - 1, left_a + half - 1);
        let most_b = min(b.len() - 1, left_b + half - 1);
        // 去掉a的前k个
        if a[most_a] <= b[most_b] {
            find_k_th(&a, most_a + 1, &b, left_b, k - (most_a - left_a + 1))
        }
        // 去掉b的前k个
        else {
            find_k_th(&a, left_a, &b, most_b + 1, k - (most_b - left_b + 1))
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::{find_k_th, Solution};

    #[test]
    fn it_find_k_th() {
        let (left_a, left_b) = find_k_th(&vec![1, 2, 3, 4], 0, &vec![2, 3, 4, 5], 0, 5);
        assert_eq!(5, left_a + left_b);
    }

    #[test]
    fn it_works1() {
        let cases = vec!((vec![1, 3], vec![2], 2.0), (vec![1, 2], vec![3, 4], 2.5), (vec![], vec![1], 1.0), (vec![], vec![1, 2, 3, 4, 5], 3.0), (vec![3], vec![-2, -1], -1.0));
        for (a, b, expected) in cases {
            println!();
            assert_eq!(Solution::find_median_sorted_arrays(a, b), expected);
        }
    }
}
